#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
// 所以 base 看起来是这样的：
// "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

class Solution 
{
public:
    // 时间复杂度 O(n)，n 是字符串 s 的长度，字符串 base 长度为正无穷
    int findSubstringInWraproundString(string s) 
    {
        int n = s.size();
        // dp[i] : s 中必须以 'a' + i 结尾的子串，最大延伸长度是多少，延伸一定要跟据 base 串的规则
        vector<int> dp(26);
        dp[s[0] - 'a'] = 1;
        for(int i = 1, cur, pre, len = 1; i < n; ++i)
        {
            cur = s[i];
            pre = s[i - 1];
            // pre cur
            if((cur == 'a' && pre == 'z') || (pre + 1 == cur))
            {
                // (前一个字符是'z' && 当前字符是'a') || 前一个字符比当前字符的 ascii 码少 1
                ++len;
            }
            else
            {
                len = 1;
            }
            dp[cur - 'a'] = max(dp[cur - 'a'], len);
        }

        return accumulate(dp.begin(), dp.end(), 0);
    }
};


class Solution 
{
public:
    // 时间复杂度 O(n)，n 是字符串 s 的长度，字符串 base 长度为正无穷
    int findSubstringInWraproundString(string s) 
    {
        int n = s.size();
        vector<int> dp(n, 1);
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == s[i - 1] + 1 || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] += dp[i - 1];
        } 

        int hash[26] = {0};
        for(int i = 0; i < n; ++i)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }

        int ret = 0;
        for(auto x : hash) ret += x;
        return ret;
    }
};